#include <queue>
#include <vector>
    int lengthOfLIS(vector<int>& nums) {
        int k = 0,i = 0;
        int* tails = new int[nums.size()+1]();
        for(; k < nums.size(); k++)
        {
            if(k == 0)
            {
                tails[++i] = nums[k];
                continue;
            }
            if(nums[k] > tails[i])
            {
                tails[++i] = nums[k];
            }
            else{
                int l = 1,r = i;
                int mid;
                while(l < r)
                {
                    mid = (l+r)/2;
                    if(tails[mid] < nums[k])
                    {
                        l = mid;
                    }
                    else{
                        r = mid;
                    }
                }
                tails[mid] = nums[k];
            }
        }
        int ans;
        for(int j = 1; j < nums.size()+1;j++)
        {
            if(tails[j]!=0)
                ans = j;
            else break;
        }
        return ans;
    }


int main() {
    // 构造空优先队列
    std::priority_queue<int> pq;
    // 指定比较函数和底层容器构造空队列
    std::priority_queue<int,std::vector<int>,std::greater<int>> pq2;
    // 以vec中{1,2,3}构造队列
    std::vector<int> vec{1,2,3,4,5};
    std::priority_queue<int> pq3(vec.begin(),vec.begin()+3);
    //指定比较函数和底层容器,并以vec构造队列
    std::priority_queue<int> pq4(std::less<int>(),vec);
    // =std::priority_queue<int,std::vector<int>,std::less<int>> pq4(std::less<int>(),vec);

    return 0;
}